import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class 电动车游城市 {
    public int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {
        // 建图, 采用动态建图的方式
        ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
        int n = charge.length;
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] path: paths) {
            graph.get(path[0]).add(new int[]{path[1],path[2]});
            graph.get(path[1]).add(new int[]{path[0],path[2]});
        }
        // 采用 dj 算法, 一样设置一个 distance 来进行记录到每个点的每个电量的距离
        int[][] distance = new int[n][cnt + 1];
        // 最开始出发的点电量为 0 并且 需要的时间也为 0
        distance[start][0] = 0;
        // 访问记录, 防止重复访问
        boolean[][] vis = new boolean[n][cnt + 1];
        // 开始全都是无穷大
        for (int[] a : distance) {
            Arrays.fill(a,Integer.MAX_VALUE);
        }
        // 0 : 当前点
        // 1 : 来到当前点的电量
        // 2 : 花费时间
        // 堆 + 比较器
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[2] - b[2]);
        heap.offer(new int[]{start,0,0});
        while (!heap.isEmpty()) {
            // 每次弹出一个
            int[] record = heap.poll();
            int cur = record[0]; // 点
            int power = record[1]; // 电量
            int cost = record[2]; // 花费的时间
            if (vis[cur][power]) {
                continue;
            }
            // 剪枝加快速度
            if (cur == end) {
                // 发现终点, 直接返回
                return cost;
            }
            vis[cur][power] = true;
            // 充电
            if (power < cnt) {
                // cnt, power + 1 每次充一格电, 并更新, 和最开始的模板其实差不多
                if (!vis[cur][power + 1] && cost + charge[cur] < distance[cur][power + 1]) {
                    distance[cur][power + 1] = cost + charge[cur];
                    heap.add(new int[]{cur,power + 1,cost + charge[cur]});
                }
            }
            for (int[] edge : graph.get(cur)) {
                // 不充电去别的城市
                int nextCity = edge[0];
                int restPower = power - edge[1];
                int nextCost = cost + edge[1];
                if (restPower >= 0 && !vis[nextCity][restPower] && nextCost < distance[nextCity][restPower]) {
                    distance[nextCity][restPower] = nextCost;
                    heap.add(new int[]{nextCity,restPower,nextCost});
                }
            }
        }
        return -1;
    }
}
